/**
 * https://leetcode-cn.com/problems/eight-queens-lcci/
 * N皇后 
 * @param n 
 * @returns 摆法的字符串 
 */
 const solveNQueens = (n: number): string[][] => {
    const ans: string[][] = []

    // 下标表示行, 值表示列
    const queues: number[] = []

    // 存放列数中是否已经被摆放了
    let cols: number = 0b0000000000000000

    //! 对角线上只要能通过当前的行和列计算出结果一样就行

    // 存放左上角 -> 右下角是否摆放过了
    let leftTop: number = 0b0000000000000000

    // 存放右下角 -> 左下角是否被拜访过了
    let rightTop: number = 0b0000000000000000


    /**
     * 摆法第row行
     * @param row 
     */
    const dfs = (row: number) => {

        // 计算值了
        if (row >= n) {
            // 得到一种摆法方法, 放入ans中

            const cur: string[] = []
            for (let i = 0; i < n; i++) {
                let s: string[] = new Array(n).fill('.')
                s[queues[i]] = 'Q'
                cur.push(s.join(''))
            }

            ans.push(cur)
            return;
        }

        /**
         * 循环列
         */
        for (let i = 0; i < n; i++) {
            // 判断列
            let co = 1 << i
            if (cols & co) continue

            // 判断左上角到右下角
            const leftIndex = 1 << (row - i)
            if (leftTop & leftIndex) continue;

            // 判断右上角到左下角
            const rightIndex = 1 << (row + i)
            if (rightTop & rightIndex) continue

            // 给列和左上角和右上角到左下角赋值为true
            cols |= co
            leftTop |= leftIndex
            rightTop |= rightIndex

            queues[row] = i

            // 摆放下一行
            dfs(row + 1)


            // 回溯了以后恢复工作
            cols &= ~co
            leftTop &= ~leftIndex
            rightTop &= ~rightIndex
        }
    }


    dfs(0)
    return ans
};


const solveNQueens3 = (n: number): string[][] => {
    const ans: string[][] = []

    // 下标表示行, 值表示列
    const queues: number[] = []

    // 存放列数中是否已经被摆放了
    const cols: boolean[] = []

    //! 对角线上只要能通过当前的行和列计算出结果一样就行

    // 存放左上角 -> 右下角是否摆放过了
    const leftTop: boolean[] = []

    // 存放右下角 -> 左下角是否被拜访过了
    const rightTop: boolean[] = []


    /**
     * 摆法第row行
     * @param row 
     */
    const dfs = (row: number) => {

        // 计算值了
        if (row >= n) {
            // 得到一种摆法方法, 放入ans中

            const cur: string[] = []
            for (let i = 0; i < n; i++) {
                let s: string[] = new Array(n).fill('.')
                s[queues[i]] = 'Q'
                cur.push(s.join(''))
            }

            ans.push(cur)
            return;
        }

        /**
         * 循环列
         */
        for (let i = 0; i < n; i++) {
            // 判断列
            if (cols[i]) continue

            // 判断左上角到右下角
            const leftIndex = row - i
            if (leftTop[leftIndex]) continue;

            // 判断右上角到左下角
            const rightIndex = row + i
            if (rightTop[rightIndex]) continue

            // 给列和左上角和右上角到左下角赋值为true
            cols[i] = leftTop[leftIndex] = rightTop[rightIndex] = true

            queues[row] = i

            // 摆放下一行
            dfs(row + 1)


            // 回溯了以后恢复工作
            cols[i] = leftTop[leftIndex] = rightTop[rightIndex] = false
        }
    }


    dfs(0)
    return ans
};


const solveNQueens2 = (n: number): string[][] => {
    const ans: string[][] = []

    // 下标表示行, 值表示列
    const queues: number[] = []



    /**
     * 摆法第row行
     * @param row 
     */
    const dfs = (row: number) => {

        // 计算值了
        if (row >= n) {
            // 得到一种摆法方法, 放入ans中

            const cur: string[] = []
            for (let i = 0; i < n; i++) {
                let s: string[] = new Array(n).fill('.')
                s[queues[i]] = 'Q'
                cur.push(s.join(''))
            }
            ans.push(cur)
            return;
        }

        /**
         * 循环列
         */
        for (let i = 0; i < n; i++) {
            if (canPlace(row, i)) {
                // 能摆放
                queues[row] = i

                // 摆放下一行
                dfs(row + 1)
            }
        }
    }

    /**
     * 判断能否在第row行摆放在第col列
     * @param row
     * @param col 
     * @returns 
     */
    const canPlace = (row: number, col: number) => {
        // 遍历之前的行
        //! 到row行就可以了 
        for (let i = 0; i < row; i++) {
            // 第i行摆放过当前列了
            if (queues[i] === col) return false

            // 对角线上有值
            if (row - i === Math.abs(col - queues[i])) {
                return false
            }
        }

        return true
    }

    dfs(0)

    return ans
};

console.log(solveNQueens(8).length)
console.log(solveNQueens(4).length)